/* vim: set sw=8 ts=8 sts=8 expandtab: */
#include "Cmaid.h"
#include "cmaid_private.h"

/* for debug only, remove after */
#include <stdio.h>

/**
 * @defgroup Cmaid_Skip_List The Skip List Implementation
 * @ingroup Implementations
 * @brief The skip list implementation
 *
 * The skip list implementation provides a tiered set of lists used for fast
 * insertions, removes and look-ups. All these operations are in approximately
 * O(log n) time. Depending on the access patterns this can become linear in
 * time, i.e. @em O(N), in the worst case scenario. The random probability used
 * to determine the form of list makes this unlikely to occur.
 *
 * The skip list is implemented with varying height nodes, so the average node
 * size should be similar to a doubly linked list.
 */

/** Type definition for the skip_list */
typedef struct Cmaid_Skip_List Cmaid_Skip_List;
/** Type definition for the skip_list node */
typedef struct Cmaid_Skip_List_Node Cmaid_Skip_List_Node;
/** Type definition for the skip_list node of the cache*/
typedef struct Cmaid_Skip_List_Cache_Node Cmaid_Skip_List_Cache_Node;
/** Type definition for the skip_list map */
typedef struct Cmaid_Skip_List_Map Cmaid_Skip_List_Map;
/** Type definition for the skip_list node of the map */
typedef struct Cmaid_Skip_List_Node_Pair Cmaid_Skip_List_Node_Pair;

#define CMAID_SKIP_LIST(h) ((Cmaid_Skip_List *)(h))
#define CMAID_SKIP_LIST_NODE(n) ((Cmaid_Skip_List_Node *)(n))
#define CMAID_SKIP_LIST_CACHE_NODE(n) ((Cmaid_Skip_List_Cache_Node *)(n))
#define CMAID_SKIP_LIST_CACHE_NODE_COUNT(n) CMAID_SKIP_LIST_CACHE_NODE(n)->count
#define CMAID_SKIP_LIST_MAP_VALUE_INFO(h) ((Cmaid_Skip_List_Map *)(h))->value_info
#define CMAID_SKIP_LIST_MAP_NODE_VALUE(n) ((Cmaid_Skip_List_Node_Pair *)(n))->value

/**
 * @internal
 * @struct The skip list node for the set
 */
struct Cmaid_Skip_List_Node
{
        Cmaid_Skip_List_Node **next;  /**< Pointer stack to the next nodes */
        void *key;                    /**< The key for the data node */
};

/**
 * @internal
 * @struct The skip_list node for the cache
 */
struct Cmaid_Skip_List_Cache_Node
{
        Cmaid_Skip_List_Node node;   /**< Inherits cache node from the node */
        unsigned int count;          /**< The count of references */
};

/**
 * @internal
 * The skip_list node for the map
 */
struct Cmaid_Skip_List_Node_Pair
{
        Cmaid_Skip_List_Node node;
        void *value;
};

/**
 * @internal
 * The base structure for the skip_list table
 */
struct Cmaid_Skip_List
{
        Cmaid_Container container;
        Cmaid_Skip_List_Node *sentinel;
        Cmaid_Iter *iter_list;
        const Cmaid_Value *key_info;
        unsigned int height;
};

/**
 * @internal
 * The extended structure for the map
 */
struct Cmaid_Skip_List_Map
{
        Cmaid_Skip_List skip_list;
        const Cmaid_Value *value_info;
};


/* Private skip_list manipulation functions */
static void cmaid_skip_list_node_add(Cmaid_Skip_List *skip_list,
                unsigned int height, Cmaid_Skip_List_Node *node);
static Cmaid_Skip_List_Node * cmaid_skip_list_node_predecessor_get(
                Cmaid_Skip_List *skip_list, Cmaid_Skip_List_Node *previous,
                const void *key, int h);
static Cmaid_Skip_List_Node * cmaid_skip_list_node_get(
                Cmaid_Skip_List *skip_list, const void *key);
static Cmaid_Skip_List_Node *cmaid_skip_list_node_remove(
                Cmaid_Skip_List *skip_list, const void *key);
static unsigned int cmaid_skip_list_height_generate(Cmaid_Skip_List *skip_list);

/* The common interface functions */
static void  cmaid_skip_list_iter_attach(Cmaid_Container *c, Cmaid_Iter *it);
static void  cmaid_skip_list_iter_detach(Cmaid_Container *c, Cmaid_Iter *it);
static void  cmaid_skip_list_destroy(Cmaid_Container *c);
static int   cmaid_skip_list_dump2(Cmaid_Container *c, FILE *file);
static void  cmaid_skip_list_clear(Cmaid_Container *c);
/* The set interface functions */
static void *cmaid_skip_list_set_add(Cmaid_Set *s, const void *data);
static void  cmaid_skip_list_set_remove(Cmaid_Set *s, const void *data);
static void *cmaid_skip_list_set_get(Cmaid_Set *s, const void *data);
CMAID_INLINE void cmaid_skip_list_single_node_free(Cmaid_Container *c, void *node);
/* The map interface functions */
static void *cmaid_skip_list_map_set(Cmaid_Map *m, const void *key,
                                        const void *data);
static void  cmaid_skip_list_map_remove(Cmaid_Map *m, const void *key);
static void *cmaid_skip_list_map_get(Cmaid_Map *m, const void *key);
static void  cmaid_skip_list_map_value_iter_attach(Cmaid_Map *m, Cmaid_Iter *it);
CMAID_INLINE void cmaid_skip_list_map_node_free(Cmaid_Container *c, void *n);
/* The cache interface functions */
static void *cmaid_skip_list_cache_instance(Cmaid_Cache *cache, const void *data);
static void  cmaid_skip_list_cache_release(Cmaid_Cache *cache, const void *data);
/* The common iterator interface functions */
static void  cmaid_skip_list_iter_start(Cmaid_Iter *it);
static void  cmaid_skip_list_iter_remove(Cmaid_Iter *it);
/* The key iter functions */
static void *cmaid_skip_list_key_iter_iter_goto(Cmaid_Iter *it, const Cmaid_Iter *to_it);
static void *cmaid_skip_list_key_iter_index_goto(Cmaid_Iter *it, int index);
static void *cmaid_skip_list_key_iter_goto(Cmaid_Iter *it, const void *data);
static void *cmaid_skip_list_key_iter_current(Cmaid_Iter *it);
static void *cmaid_skip_list_key_iter_next(Cmaid_Iter *it);
static void *cmaid_skip_list_key_iter_previous(Cmaid_Iter *it);
/* The value iter functions */
static void *cmaid_skip_list_value_iter_iter_goto(Cmaid_Iter *it, const Cmaid_Iter *to_it);
static void *cmaid_skip_list_value_iter_index_goto(Cmaid_Iter *it, int index);
static void *cmaid_skip_list_value_iter_goto(Cmaid_Iter *it, const void *data);
static void *cmaid_skip_list_value_iter_current(Cmaid_Iter *it);
static void *cmaid_skip_list_value_iter_next(Cmaid_Iter *it);
static void *cmaid_skip_list_value_iter_previous(Cmaid_Iter *it);
/* Iter helper */
static Cmaid_Skip_List_Node *cmaid_skip_list_iter_next(Cmaid_Iter *it);
static Cmaid_Skip_List_Node *cmaid_skip_list_iter_previous(Cmaid_Iter *it);

/*
 * The Interfaces
 */
const Cmaid_Set_Interface cmaid_skip_list_set_if =
{
        {
                CMAID_MAGIC_SET,
                cmaid_skip_list_clear,
                cmaid_skip_list_iter_attach,
                cmaid_skip_list_iter_detach,
                cmaid_skip_list_destroy,
                cmaid_skip_list_dump2,
                cmaid_skip_list_single_node_free
        },
        cmaid_skip_list_set_add,
        cmaid_skip_list_set_remove,
        cmaid_skip_list_set_get
};

const Cmaid_Map_Interface cmaid_skip_list_map_if =
{
        {
                CMAID_MAGIC_MAP,
                cmaid_skip_list_clear,
                cmaid_skip_list_iter_attach,
                cmaid_skip_list_iter_detach,
                cmaid_skip_list_destroy,
                cmaid_skip_list_dump2,
                cmaid_skip_list_map_node_free
        },
        cmaid_skip_list_map_set,
        cmaid_skip_list_map_remove,
        cmaid_skip_list_map_get,
        cmaid_skip_list_map_value_iter_attach
};

const Cmaid_Cache_Interface cmaid_skip_list_cache_if =
{
        {
                CMAID_MAGIC_CACHE,
                cmaid_skip_list_clear,
                cmaid_skip_list_iter_attach,
                cmaid_skip_list_iter_detach,
                cmaid_skip_list_destroy,
                cmaid_skip_list_dump2,
                cmaid_skip_list_single_node_free
        },
        cmaid_skip_list_cache_instance,
        cmaid_skip_list_cache_release
};

const Cmaid_Iter_Interface cmaid_skip_list_key_iter_if =
{
        cmaid_skip_list_iter_start,
        cmaid_skip_list_key_iter_iter_goto,
        cmaid_skip_list_key_iter_index_goto,
        cmaid_skip_list_key_iter_goto,
        cmaid_skip_list_key_iter_current,
        cmaid_skip_list_key_iter_next,
        cmaid_skip_list_key_iter_previous,
        cmaid_skip_list_iter_remove
};

const Cmaid_Iter_Interface cmaid_skip_list_value_iter_if =
{
        cmaid_skip_list_iter_start,
        cmaid_skip_list_value_iter_iter_goto,
        cmaid_skip_list_value_iter_index_goto,
        cmaid_skip_list_value_iter_goto,
        cmaid_skip_list_value_iter_current,
        cmaid_skip_list_value_iter_next,
        cmaid_skip_list_value_iter_previous,
        cmaid_skip_list_iter_remove
};

/*
 * Utility functions
 */

static void 
cmaid_skip_list_dump(Cmaid_Skip_List *skip_list)
{
        int i;
        Cmaid_Skip_List_Node *previous;

        for (i = skip_list->height - 1; i >= 0; i--)
        {
                previous = skip_list->sentinel;
                printf("Level %d of %d\n%p", i, skip_list->height,
                                previous);
                while (previous->next[i] != skip_list->sentinel)
                {
                        printf("->%p", previous->next[i]);
                        previous = previous->next[i];
                }
                printf("\n");
        }

        return;
}

static void 
cmaid_skip_list_iter_dump(Cmaid_Skip_List *skip_list)
{
        Cmaid_Iter *iter;

        for (iter = skip_list->iter_list; iter; iter = iter->next)
        {
                printf("Iter %p: index %d of %d\n", iter, iter->index,
                                CMAID_CONTAINER(skip_list)->count);
        }

        return;
}

static void
cmaid_skip_list_node_pointers_init(Cmaid_Skip_List *skip_list, 
                Cmaid_Skip_List_Node *node, unsigned int height)
{
        int i;

        for (i = 0; i < height; i++)
                node->next[i] = skip_list->sentinel;

        return;
}

static unsigned int
cmaid_skip_list_init(Cmaid_Skip_List *new_skip_list, unsigned int height)
{
        new_skip_list->height = height;
        return 1;
}

static Cmaid_Skip_List_Node *
cmaid_skip_list_node_predecessor_get(Cmaid_Skip_List *skip_list,
                                     Cmaid_Skip_List_Node *previous,
                                     const void *key, int h)
{
        if (skip_list->key_info->cmp)
        {
                while (previous->next[h] != skip_list->sentinel)
                {
                        if (skip_list->key_info->cmp(previous->next[h]->key,
                                                key) >= 0)
                                break;
                        previous = previous->next[h];
                }
        }
        else
        {
                while (previous->next[h] != skip_list->sentinel)
                {
                        if (previous->next[h]->key >= key)
                                break;
                        previous = previous->next[h];
                }
        }

        return previous;
}

CMAID_INLINE void
cmaid_skip_list_iter_update_add(Cmaid_Skip_List *skip_list,
                                Cmaid_Skip_List_Node *node)
{
        Cmaid_Iter *iter;

        if (skip_list->key_info->cmp)
        {
                for (iter = skip_list->iter_list; iter; iter = iter->next)
                {
                        if (iter->current != skip_list->sentinel &&
                                        skip_list->key_info->cmp(
                                                CMAID_SKIP_LIST_NODE(
                                                        iter->current)->key,
                                                node->key) >= 0)
                                iter->index++;
                }
        }
        else
        {
                for (iter = skip_list->iter_list; iter; iter = iter->next)
                {
                        if (iter->current != skip_list->sentinel &&
                                        CMAID_SKIP_LIST_NODE(iter->current)->key
                                        >= node->key)
                                iter->index++;
                }
        }
}

CMAID_INLINE void
cmaid_skip_list_iter_update_remove(Cmaid_Skip_List *skip_list,
                                   Cmaid_Skip_List_Node *previous,
                                   Cmaid_Skip_List_Node *node)
{
        Cmaid_Iter *iter;

        for (iter = skip_list->iter_list; iter; iter = iter->next)
        {
                if (iter->current != skip_list->sentinel)
                {
                        int compare;

                        if (skip_list->key_info->cmp)
                                compare = skip_list->key_info->cmp(
                                                CMAID_SKIP_LIST_NODE(
                                                        iter->current)->key,
                                                node->key);
                        else
                                compare = CMAID_SKIP_LIST_NODE(
                                                iter->current)->key - node->key;

                        if (!compare)
                        {
                                iter->current = previous;
                                iter->index--;
                        }
                        else if (compare > 0 && iter->index > 0)
                                iter->index--;

                        if (iter->current == skip_list->sentinel)
                                cmaid_skip_list_iter_start(iter);
                }
        }
}

/*
 * Node Functions
 */
CMAID_INLINE Cmaid_Skip_List_Node *
cmaid_skip_list_set_node_new(Cmaid_Skip_List *skip_list, unsigned int height,
                const void *key)
{
        void *val;
        Cmaid_Skip_List_Node *node;
        
        node = cmaid_single_node_new(sizeof(Cmaid_Skip_List_Node) +
                        (height * sizeof(Cmaid_Skip_List_Node *)),
                        skip_list->key_info, key, 0, &val);
        if (!node)
                return NULL;

        node->next = (Cmaid_Skip_List_Node **)((char *)node +
                        sizeof(Cmaid_Skip_List_Node));
        node->key = val;
        cmaid_skip_list_node_pointers_init(skip_list, node, height);

        return node;
}

CMAID_INLINE Cmaid_Skip_List_Node *
cmaid_skip_list_map_node_new(Cmaid_Skip_List *skip_list, unsigned int height,
                const void *key, const void *value)
{
        void *kptr;
        void *vptr;
        Cmaid_Skip_List_Node *node;

        node = cmaid_pair_node_new(sizeof(Cmaid_Skip_List_Node_Pair) +
                        (height * sizeof(Cmaid_Skip_List_Node *)),
                        skip_list->key_info, key, 0, &kptr,
                        CMAID_SKIP_LIST_MAP_VALUE_INFO(skip_list), value, 0,
                        &vptr);
        if (!node)
                return NULL;

        node->next = (Cmaid_Skip_List_Node **)((char *)node +
                        sizeof(Cmaid_Skip_List_Node_Pair));
        node->key = kptr;
        CMAID_SKIP_LIST_MAP_NODE_VALUE(node) = vptr;
        cmaid_skip_list_node_pointers_init(skip_list, node, height);

        return node;
}

CMAID_INLINE Cmaid_Skip_List_Node *
cmaid_skip_list_cache_node_new(Cmaid_Skip_List *skip_list, unsigned int height,
                const void *key)
{
        void *val;
        Cmaid_Skip_List_Node *node;
        
        node = cmaid_single_node_new(sizeof(Cmaid_Skip_List_Cache_Node) +
                        (height * sizeof(Cmaid_Skip_List_Cache_Node *)),
                        skip_list->key_info, key, 0, &val);
        if (!node)
                return NULL;

        node->next = (Cmaid_Skip_List_Node **)((char *)node +
                        sizeof(Cmaid_Skip_List_Cache_Node));
        node->key = val;
        CMAID_SKIP_LIST_CACHE_NODE_COUNT(node) = 1;
        cmaid_skip_list_node_pointers_init(skip_list, node, height);

        return node;
}

CMAID_INLINE void
cmaid_skip_list_single_node_free(Cmaid_Container *c, void *n)
{
        Cmaid_Skip_List *skip_list = CMAID_SKIP_LIST(c);
        Cmaid_Skip_List_Node *node = n;
        cmaid_single_node_free(node, skip_list->key_info, node->key);
}

CMAID_INLINE void
cmaid_skip_list_map_node_free(Cmaid_Container *c, void *n)
{
        Cmaid_Skip_List *skip_list = CMAID_SKIP_LIST(c);
        Cmaid_Skip_List_Node *node = n;
        cmaid_pair_node_free(node, skip_list->key_info, node->key,
                                CMAID_SKIP_LIST_MAP_VALUE_INFO(skip_list),
                                CMAID_SKIP_LIST_MAP_NODE_VALUE(node));
}

/*
 * Common Interface Functions
 */
static void
cmaid_skip_list_iter_attach(Cmaid_Container *c, Cmaid_Iter *it)
{
        it->interface = &cmaid_skip_list_key_iter_if;
        it->container = c;
        cmaid_skip_list_iter_start(it);

        /* insert into the iter list */
        it->next = CMAID_SKIP_LIST(c)->iter_list;
        CMAID_SKIP_LIST(c)->iter_list = it;        
}

static void
cmaid_skip_list_iter_detach(Cmaid_Container *c, Cmaid_Iter *it)
{
        Cmaid_Skip_List *skip_list = CMAID_SKIP_LIST(c);
        cmaid_iterlist_remove(&skip_list->iter_list, it);
}

static void 
cmaid_skip_list_clear(Cmaid_Container *c)
{
        Cmaid_Skip_List *skip_list = CMAID_SKIP_LIST(c);
        Cmaid_Container_Node_Free_Cb node_free;
        int i;

        node_free = CMAID_CONTAINER_FUNC(c)->node_free;

        while (skip_list->sentinel->next[0] != skip_list->sentinel)
        {
                Cmaid_Skip_List_Node *node;

                node = skip_list->sentinel->next[0];
                skip_list->sentinel->next[0] = node->next[0];
                node_free(CMAID_CONTAINER(skip_list), node);
        }

        CMAID_CONTAINER(skip_list)->count = 0;

        /* Reset the sentinel pointers at all levels. */
        for (i = 0; i < skip_list->height; i++)
                skip_list->sentinel->next[i] = skip_list->sentinel;

        return;
}

static void 
cmaid_skip_list_destroy(Cmaid_Container *c)
{
        Cmaid_Skip_List *skip_list = CMAID_SKIP_LIST(c);

        cmaid_container_clear(c);

        FREE(skip_list->sentinel);
        FREE(c);

        return;
}

static void
cmaid_skip_list_dump_node(Cmaid_Skip_List_Node *node, FILE *file,
                const char *name, const char *label, unsigned int h,
                unsigned int print_links)
{
        unsigned int i;

        /* first print the node */
        if (!name)
                fprintf(file, "\tn%p [\n\t\tlabel=\"%s", node, label);
        else
                fprintf(file, "\t%s [\n\t\tlabel=\"%s", name, label);

        for (i = 0; i < h; i++)
                fprintf(file, " | <f%d> %d", i, i);
        fprintf(file, "\"\n\t\tshape=\"record\"\n\t];\n");
        
        /* and the links of the node */
        if (print_links)
        {
                for (i = 0; i < h; i++)
                {
                        if (!name)
                                fprintf(file, "\tn%p:f%d -> n%p:f%d;\n",
                                                node, i, node->next[i], i);
                        else
                                fprintf(file, "\t%s:f%d -> n%p:f%d;\n",
                                                name, i, node->next[i], i);
                }
        }
}

static void
cmaid_skip_list_dump_everything_between(Cmaid_Skip_List_Node *start,
                Cmaid_Skip_List_Node *end, FILE *file,
                Cmaid_Value_Stringify_Cb cb, char *buffer, size_t size,
                unsigned int h)
{
        Cmaid_Skip_List_Node *node, *prev;

        /* if the height is zero there is no node between them */
        if (h == 0)
                return;

        prev = start;
        node = start->next[h - 1];
        for (;;)
        {
                /* first print all nodes between start and the current one */
                cmaid_skip_list_dump_everything_between(prev, node,
                                        file, cb, buffer, size, h - 1);

                /* we do this here and not in the for statement to be sure
                 * that we look for nodes between end and prev */
                if (node == end)
                        break;

                /* and now print the node itself */
                cb(node->key, buffer, size);
                cmaid_skip_list_dump_node(node, file, NULL, buffer, h, 1);
                /* save the old node */
                prev = node;
                node = node->next[h - 1];
        }
}

static int
cmaid_skip_list_dump2(Cmaid_Container *c, FILE *file)
{
        Cmaid_Skip_List *skip_list = CMAID_SKIP_LIST(c);
        Cmaid_Value_Stringify_Cb cb;
        char buffer[1024];
        unsigned int h;

        h = skip_list->height;

        /* the header */
        fprintf(file, "digraph skip_list%p {\n", c);
        /* dump the sentinel, we are doing this twice for a better layout
         * the first one will only have outgoing links the second one will
         * only have incomming links that way we unroll the circular nature
         * of the list */
        cmaid_skip_list_dump_node(skip_list->sentinel, file, "sentinel",
                        "sentinel", h, 1);
        cb = skip_list->key_info->stringify ? skip_list->key_info->stringify
                : cmaid_value_pointer_stringify;
        /* and now dump everything between it */
        cmaid_skip_list_dump_everything_between(skip_list->sentinel,
                        skip_list->sentinel, file, cb, buffer, sizeof(buffer),
                        h);
        /* and here the second sentinel */
        cmaid_skip_list_dump_node(skip_list->sentinel, file, NULL, "sentinel",
                        h, 0);
        fprintf(file, "}\n");
}

/*
 * The Set Interface Functions
 */
/**
 * @param height The maximum height of any node in the skip list. A larger value
 *        results in faster traversal but more memory usage. Suggested initial
 *        value is 4 and tweak it as necessary later.
 * @param v The @ref Cmaid_Value "value structure" defining the type of the
 *        objects used in the set
 * @return Returns a newly allocated @ref Cmaid_Set "set", an allocation error
 *        occurs, @c NULL is returned
 * @brief Creates a new set using the skip_list implementation
 *
 * This functions is creating a @ref Cmaid_Set "set" with the skip list
 * as implementation
 */
Cmaid_Set *
cmaid_skip_list_set_new(unsigned int height, const Cmaid_Value *v)
{
        Cmaid_Skip_List *new_skip_list = CALLOC(1, sizeof(Cmaid_Skip_List));
        if (!new_skip_list)
                return NULL;

        CMAID_CONTAINER_INTERFACE_SET(new_skip_list, &cmaid_skip_list_set_if);

        new_skip_list->sentinel = cmaid_skip_list_set_node_new(new_skip_list,
                        height, NULL);
        cmaid_skip_list_node_pointers_init(new_skip_list,
                        new_skip_list->sentinel, height);

        /* Setup the sentinel before the value to avoid size detection. */
        if (!new_skip_list->sentinel)
        {
                FREE(new_skip_list);
                return NULL;
        }

        if (v)
                new_skip_list->key_info = v;
        else
                new_skip_list->key_info = &cmaid_value_pointer;

        if (!cmaid_skip_list_init(new_skip_list, height))
        {
                FREE(new_skip_list);
                return NULL;
        }

        return (Cmaid_Set *)new_skip_list;
}

static void *
cmaid_skip_list_set_add(Cmaid_Set *set, const void *key)
{
        Cmaid_Skip_List *skip_list = CMAID_SKIP_LIST(set);
        Cmaid_Skip_List_Node *node;
        unsigned int size = 0;

        /* TODO(ningerso): This is another place where we could avoid two
         * lookups. */
        node = cmaid_skip_list_node_get(skip_list, key);

        if (node)
        {
                /* TODO(ningerso): Is this the desired behavior? It seems
                 * dangerous to free external data. */
                /* (pfritz): Since there is no dup function, but a free function
                 * we are already the owner of the data, so it is up to us to
                 * free it if we do not need it anylonger, an example might be
                 * a common ecore_data pattern:
                 *
                 * cmaid_map_add(map, strdup("bla"), data);
                 */
                if (skip_list->key_info->pointer.free &&
                                !skip_list->key_info->pointer.dup) 
                        skip_list->key_info->pointer.free((void *)key);
        }
        else
        {
                unsigned int h = cmaid_skip_list_height_generate(skip_list);

                node = cmaid_skip_list_set_node_new(skip_list, h, key);
                cmaid_skip_list_node_add(skip_list, h, node);
        }


        return node->key;
}

static void
cmaid_skip_list_set_remove(Cmaid_Set *set, const void *key)
{
        Cmaid_Skip_List_Node *node;
        unsigned int dummy;
        Cmaid_Skip_List *skip_list = CMAID_SKIP_LIST(set);

        /* Compute the position in the table */
        node = cmaid_skip_list_node_remove(skip_list, key);
        if (!node)
                return;

        cmaid_skip_list_single_node_free(set, node);
}

static void *
cmaid_skip_list_set_get(Cmaid_Set *set, const void *key)
{
        Cmaid_Skip_List_Node *node;
        unsigned int dummy;
        Cmaid_Skip_List *skip_list = CMAID_SKIP_LIST(set);

        node = cmaid_skip_list_node_get(skip_list, key);
        if (!node)
                return NULL;

        return node->key;
}

/*
 * Cache Interface Functions
 */
/**
 * @param v The @ref Cmaid_Value "value structure" defining the type of the
 *        objects that are cached.
 * @return Returns a newly allocated @ref Cmaid_Cache "cache", an allocation
 *        error  occurs, @c NULL is returned
 * @brief Creates a new cache using the skip_list implementation
 *
 * This functions is creating a @ref Cmaid_Cache "cache" with the skip_list table
 * as implementation.
 */
Cmaid_Cache *
cmaid_skip_list_cache_new(const Cmaid_Value *v)
{
        Cmaid_Skip_List *new_skip_list = (Cmaid_Skip_List *)CALLOC(1, sizeof(Cmaid_Skip_List));
        if (!new_skip_list)
                return NULL;

        CMAID_CONTAINER_INTERFACE_SET(new_skip_list, &cmaid_skip_list_cache_if);
        if (v)
                new_skip_list->key_info = v;
        else
                new_skip_list->key_info = &cmaid_value_pointer;

        return (Cmaid_Cache *)new_skip_list;
}

static void *
cmaid_skip_list_cache_instance(Cmaid_Cache *c, const void *key)
{
        Cmaid_Skip_List *skip_list = CMAID_SKIP_LIST(c);
        Cmaid_Skip_List_Node *node;
        unsigned int size = 0;

        node = cmaid_skip_list_node_get(skip_list, key);

        if (node)
        {
                if (skip_list->key_info->pointer.free 
                                && !skip_list->key_info->pointer.dup) 
                        skip_list->key_info->pointer.free((void *)key);
                CMAID_SKIP_LIST_CACHE_NODE_COUNT(node)++;
        }
        else
        {
                void *val;
                unsigned int h;

                h = cmaid_skip_list_height_generate(skip_list);
                node = cmaid_skip_list_cache_node_new(skip_list, h, key);
                if (!node)
                        return NULL;

                cmaid_skip_list_node_add(skip_list, h, node);
                return node->key;
        }

        return node->key;
}

static void
cmaid_skip_list_cache_release(Cmaid_Cache *c, const void *key)
{
        Cmaid_Skip_List *skip_list = CMAID_SKIP_LIST(c);
        Cmaid_Skip_List_Node *node;
        Cmaid_Skip_List_Node *prev = NULL;
        unsigned int dummy;

        if (skip_list->sentinel->next[0] == skip_list->sentinel)
                return;

        /* TODO(ningerso): This could be potentially optimized to avoid two
         * lookups for the check/remove */
        node = cmaid_skip_list_node_get(skip_list, key);
        if (!node)
                return;

        /* TODO(ningerso): Implement the actual removal. */
        if (--CMAID_SKIP_LIST_CACHE_NODE_COUNT(node) == 0)
        {
                /* ok we have actually to remove the node */
                /* first update the iters */
                /* TODO(ningerso): Fix this call once the removal is
                 * implemented. */
                cmaid_skip_list_iter_update_remove(skip_list, NULL, node);
                /*remove the node */
                cmaid_skip_list_node_remove(skip_list, key);

                /* and reduce the count */
                CMAID_CONTAINER(skip_list)->count--;

                cmaid_skip_list_single_node_free(c, node);
        }
}

/*
 * The Map Interface Functions
 */
static void
cmaid_skip_list_map_value_iter_attach(Cmaid_Container *c, Cmaid_Iter *it)
{
        it->interface = &cmaid_skip_list_value_iter_if;
        it->container = c;
        cmaid_skip_list_iter_start(it);

        /* insert into the iter list */
        it->next = CMAID_SKIP_LIST(c)->iter_list;
        CMAID_SKIP_LIST(c)->iter_list = it;        
}

/**
 * @param height The maximum height of any node in the skip list. A larger value
 *        results in faster traversal but more memory usage. Suggested initial
 *        value is 4 and tweak it as necessary later.
 * @param key The @ref Cmaid_Value "value structure" defining the type of the
 *        objects used for the key object.
 * @param value The @ref Cmaid_Value "value structure" defining the type of the
 *        objects used for the value object.
 * @return Returns a newly allocated @ref Cmaid_Map "map", an allocation error
 *        occurs, @c NULL is returned.
 * @brief Creates a new map using the skip_list implementation
 *
 * This functions is creating a @ref Cmaid_Map "map" with the skip_list table as
 * implementation.
 */
Cmaid_Map *
cmaid_skip_list_map_new(unsigned int height, const Cmaid_Value *key,
                const Cmaid_Value *value)
{
        Cmaid_Skip_List *new_skip_list = CALLOC(1, sizeof(Cmaid_Skip_List_Map));
        if (!new_skip_list)
                return NULL;

        new_skip_list->sentinel = cmaid_skip_list_map_node_new(new_skip_list,
                        height, NULL, NULL);
        cmaid_skip_list_node_pointers_init(new_skip_list,
                        new_skip_list->sentinel, height);

        CMAID_CONTAINER_INTERFACE_SET(new_skip_list, &cmaid_skip_list_map_if);
        if (key)
                new_skip_list->key_info = key;
        else
                new_skip_list->key_info = &cmaid_value_pointer;

        if (value)
                CMAID_SKIP_LIST_MAP_VALUE_INFO(new_skip_list) = value;
        else
                CMAID_SKIP_LIST_MAP_VALUE_INFO(new_skip_list) =
                        &cmaid_value_pointer;

        if (!new_skip_list->sentinel)
        {
                FREE(new_skip_list);
                return NULL;
        }

        if (!cmaid_skip_list_init(new_skip_list, height))
        {
                FREE(new_skip_list);
                return NULL;
        }

        return (Cmaid_Map *)new_skip_list;
}

static void *
cmaid_skip_list_map_set(Cmaid_Map *map, const void *key, const void *value)
{
        void *vptr;
        void *kptr;
        unsigned int h;
        Cmaid_Skip_List_Node *node;
        Cmaid_Skip_List *skip_list = CMAID_SKIP_LIST(map);

        if (value == NULL)
                cmaid_skip_list_map_remove(map, key);

        node = cmaid_skip_list_node_remove(skip_list, key);
        if (node)
                cmaid_skip_list_map_node_free(map, node);

        h = cmaid_skip_list_height_generate(skip_list);
        node = cmaid_skip_list_map_node_new(skip_list, h, key, value);
        if (!node)
                return NULL;

        cmaid_skip_list_node_add(skip_list, h, node);

        return node->key;
}

static void
cmaid_skip_list_map_remove(Cmaid_Map *map, const void *key)
{
        Cmaid_Skip_List_Node *node;
        unsigned int dummy;
        Cmaid_Skip_List *skip_list = CMAID_SKIP_LIST(map);

        /* Compute the position in the table */
        node = cmaid_skip_list_node_remove(skip_list, key);
        if (!node)
                return;

        cmaid_skip_list_map_node_free(map, node);
}

static void *
cmaid_skip_list_map_get(Cmaid_Map *map, const void *key)
{
        Cmaid_Skip_List_Node *node;
        unsigned int dummy;
        Cmaid_Skip_List *skip_list = CMAID_SKIP_LIST(map);

        node = cmaid_skip_list_node_get(skip_list, key);
        if (!node)
                return NULL;

        return CMAID_SKIP_LIST_MAP_NODE_VALUE(node);
}

static unsigned int
cmaid_skip_list_height_generate(Cmaid_Skip_List *skip_list)
{
        unsigned int h;
        unsigned int generator;

        generator = rand();

        /* roll until we find the insertion height */
        for (h = 1; h < skip_list->height; h++)
        {
                if (generator & 1)
                        break;
                generator >>= 1;
        }

        return h;
}

/*
 * Helper functions
 */
static void
cmaid_skip_list_node_add(Cmaid_Skip_List *skip_list, unsigned int height,
                Cmaid_Skip_List_Node *node)
{
        unsigned int generator;
        int i;
        Cmaid_Skip_List_Node *previous;

        /* walk to the predecessor at each height using the predecessor at the
         * previous height as the starting point to avoid walking duplicate
         * nodes */
        previous = skip_list->sentinel;
        for (i = skip_list->height - 1; i >= 0; i--)
        {
                previous = cmaid_skip_list_node_predecessor_get(skip_list,
                                previous, node->key, i);
                if (i < height)
                {
                        node->next[i] = previous->next[i];
                        previous->next[i] = node;
                }
        }

        cmaid_skip_list_iter_update_add(skip_list, node);
        CMAID_CONTAINER(skip_list)->count++;
}

static Cmaid_Skip_List_Node *
cmaid_skip_list_node_get(Cmaid_Skip_List *skip_list, const void *key)
{
        int i;
        Cmaid_Value_Compare_Cb cmp;
        Cmaid_Skip_List_Node *prev = NULL;

        prev = skip_list->sentinel;
        cmp = skip_list->key_info->cmp ? skip_list->key_info->cmp
                : cmaid_value_pointer_compare;

        for (i = skip_list->height - 1; i >= 0; i--)
        {
                /* Keeping this in the loop because the loop logic can break in
                 * subtle ways and I'd prefer to not duplicate it. Using a local
                 * variable to minimize pointer dereferences. */
                while (prev->next[i] != skip_list->sentinel)
                {
                        int comparison;
                        
                        comparison = cmp(prev->next[i]->key, key);
                        if (comparison < 0)
                                prev = prev->next[i];
                        else if (comparison == 0)
                                /* We have found the node! */
                                return prev->next[i];
                        else
                                /* The node is not in this skip list level.
                                 * Breaking here will cause the for loop to
                                 * look a level deeper */
                                break;
                }
        }

        /* The key is not in the list */
        return NULL;
}

static Cmaid_Skip_List_Node *
cmaid_skip_list_node_remove(Cmaid_Skip_List *skip_list, const void *key)
{
        int i;
        Cmaid_Value_Compare_Cb cmp;
        Cmaid_Skip_List_Node *node;
        Cmaid_Skip_List_Node *previous;

        node = NULL;
        cmp = skip_list->key_info->cmp;
        previous = skip_list->sentinel;

        for (i = skip_list->height - 1; i >= 0; i--)
        {
                int comparison;

                previous = cmaid_skip_list_node_predecessor_get(skip_list,
                                previous, key, i);

                /* Avoid comparison of the sentinel node as it has a special
                 * value */
                if (previous->next[i] == skip_list->sentinel)
                        continue;

                if (cmp)
                        comparison = cmp(previous->next[i]->key, key);
                else
                        comparison = previous->next[i]->key - key;

                /* Found the node at this level, so drop it from the list */
                if (!comparison)
                {
                        node = previous->next[i];
                        previous->next[i] = node->next[i];
                }
        }

        if (node)
        {
                CMAID_CONTAINER(skip_list)->count--;
                cmaid_skip_list_iter_update_remove(skip_list, previous, node);
        }

        return node;
}

/*
 * The Iterator functions
 */
/* The common iterator interface functions */
static void
cmaid_skip_list_iter_start(Cmaid_Iter *it)
{
        it->current = CMAID_SKIP_LIST(it->container)->sentinel;
        it->index = -1;
}

static void
cmaid_skip_list_iter_remove(Cmaid_Iter *it)
{
        Cmaid_Skip_List *skip_list = CMAID_SKIP_LIST(it->container);
        Cmaid_Container *c = CMAID_CONTAINER(skip_list);

        if (it->current)
        {
                Cmaid_Skip_List_Node *node;

                node = cmaid_skip_list_node_remove(skip_list,
                                CMAID_SKIP_LIST_NODE(it->current)->key);
                CMAID_CONTAINER_FUNC(c)->node_free(c, node);
        }
}

/* helper functions */
static Cmaid_Skip_List_Node *
cmaid_skip_list_iter_next(Cmaid_Iter *it)
{
        const Cmaid_Skip_List *skip_list = CMAID_SKIP_LIST(it->container);

        if (CMAID_SKIP_LIST_NODE(it->current)->next[0] != skip_list->sentinel)
        {
                it->index++;
                return it->current = CMAID_SKIP_LIST_NODE(it->current)->next[0];
        }

        /* we are at the end */
        cmaid_skip_list_iter_start(it);
        return NULL;
}

static Cmaid_Skip_List_Node *
cmaid_skip_list_iter_previous(Cmaid_Iter *it)
{
        int i;
        Cmaid_Skip_List_Node *search;
        Cmaid_Skip_List *skip_list = CMAID_SKIP_LIST(it->container);

        search = it->current;

        cmaid_skip_list_iter_start(it);
        while (CMAID_SKIP_LIST_NODE(it->current)->next[0]
                        != skip_list->sentinel)
        {
                if (CMAID_SKIP_LIST_NODE(it->current)->next[0] == search)
                        break;
                cmaid_skip_list_iter_next(it);
        }

        if (it->current == skip_list->sentinel)
        {
                cmaid_skip_list_iter_start(it);
                return NULL;
        }

        return it->current;
}

static Cmaid_Skip_List_Node *
cmaid_skip_list_iter_index_goto(Cmaid_Iter *it, int index)
{
        const int count = CMAID_CONTAINER(it->container)->count;
        int i;

        if (count == 0 || index >= count || index < 0)
        {
                cmaid_skip_list_iter_start(it);
                return NULL;
        }

        if (index < it->index)
                cmaid_skip_list_iter_start(it);

        for (i = it->index; i != index; i++)
                cmaid_skip_list_iter_next(it);

        return it->current;
}

/* The key iter functions */
static void *
cmaid_skip_list_key_iter_iter_goto(Cmaid_Iter *it, const Cmaid_Iter *to_it)
{
        if (!to_it || it->container != to_it->container)
                return NULL;

        it->index = to_it->index;
        it->current = to_it->current;
        return (it->current) ? CMAID_SKIP_LIST_NODE(it->current)->key : NULL;
}

static void *
cmaid_skip_list_key_iter_index_goto(Cmaid_Iter *it, int index)
{
        Cmaid_Skip_List_Node *node = cmaid_skip_list_iter_index_goto(it, index);
        return (node) ? node->key : NULL;
}

static void *
cmaid_skip_list_key_iter_goto(Cmaid_Iter *it, const void *data)
{
        void * found;

        cmaid_skip_list_iter_start(it);
        while ((found = cmaid_skip_list_key_iter_next(it)) && found != data)
                ;

        return found;
}

static void *
cmaid_skip_list_key_iter_current(Cmaid_Iter *it)
{
        return (it->current) ? CMAID_SKIP_LIST_NODE(it->current)->key : NULL;
}

static void *
cmaid_skip_list_key_iter_next(Cmaid_Iter *it)
{
        Cmaid_Skip_List_Node *node = cmaid_skip_list_iter_next(it);
        return (node) ? node->key : NULL;
}

static void *
cmaid_skip_list_key_iter_previous(Cmaid_Iter *it)
{
        Cmaid_Skip_List_Node *node = cmaid_skip_list_iter_previous(it);
        return (node) ? node->key : NULL;
}

/* The value iter functions */
static void *
cmaid_skip_list_value_iter_iter_goto(Cmaid_Iter *it, const Cmaid_Iter *to_it)
{
        if (!to_it || it->container != to_it->container)
                return NULL;

        it->index = to_it->index;
        it->current = to_it->current;
        return (it->current) ? CMAID_SKIP_LIST_MAP_NODE_VALUE(it->current) : NULL;
}
static void *
cmaid_skip_list_value_iter_index_goto(Cmaid_Iter *it, int index)
{
        Cmaid_Skip_List_Node *node = cmaid_skip_list_iter_index_goto(it, index);
        return (node) ? CMAID_SKIP_LIST_MAP_NODE_VALUE(node) : NULL;
}

static void *
cmaid_skip_list_value_iter_goto(Cmaid_Iter *it, const void *data)
{
        void * found;

        cmaid_skip_list_iter_start(it);
        while ((found = cmaid_skip_list_value_iter_next(it)) && found != data)
                ;

        return found;
}

static void *
cmaid_skip_list_value_iter_current(Cmaid_Iter *it)
{
        return (it->current) ? CMAID_SKIP_LIST_MAP_NODE_VALUE(it->current) : NULL;
}

static void *
cmaid_skip_list_value_iter_next(Cmaid_Iter *it)
{
        Cmaid_Skip_List_Node *node = cmaid_skip_list_iter_next(it);
        return (node) ? CMAID_SKIP_LIST_MAP_NODE_VALUE(node) : NULL;
}

static void *
cmaid_skip_list_value_iter_previous(Cmaid_Iter *it)
{
        Cmaid_Skip_List_Node *node = cmaid_skip_list_iter_previous(it);
        return (node) ? CMAID_SKIP_LIST_MAP_NODE_VALUE(node) : NULL;
}
